package leetcode_100;

import java.util.ArrayList;
import java.util.List;

/**
 *@author 周杨
 *NQueens_51 N皇后问题 构造n*n棋盘  保证每个皇后不在同一直线、斜线上  
 *describe: 回溯法解决 AC 71%
 *2018年5月6日 下午3:36:32
 */
public class NQueens_51 {
	List<List<String>> res=new ArrayList<List<String>>();
	boolean board[][];
	int n;
	public static void main(String[] args) {
		NQueens_51 test=new NQueens_51();
		test.solveNQueens(4);

	}
	
	public List<List<String>> solveNQueens(int n) {
		this.board=new boolean [n][n];
		this.n=n;
		help(0);
        return this.res;
    }
	
	public void help(int count) {
		if(count==this.n) {
			List<String> list=new ArrayList<String>();
			for(int i=0;i<this.n;++i) {//
				StringBuffer sb=new StringBuffer();
				for(int j=0;j<this.n;++j) {//一行是一个String
					if(board[i][j])
						sb.append("Q");
					else
						sb.append(".");
				}
				list.add(sb.toString());
			}
			this.res.add(list);
			return;
		}
		for(int i=0;i<this.n;++i) {
			if(judge(count,i)) {//可以放
				board[count][i]=true;
				help(count+1);
				board[count][i]=false;
			}
		}
	}
	
	public void print() {
		for(int i=0;i<this.n;++i) {
			for(int j=0;j<this.n;++j) {
			System.out.print(board[i][j]+" ");	
			}
			System.out.println();
		}
	}
	
	public boolean judge(int x,int y) {
		for(int i=0;i<n;++i) {//检查横向纵向
			if(board[i][y])
				return false;
			if(board[x][i])
				return false;
		}
		int count=1;
		while(x+count<n&&y+count<n) {
			if(board[x+count][y+count])
				return false;
			++count;
		}
		count=1;
		while(x-count>=0&&y-count>=0) {
			if(board[x-count][y-count])
				return false;
			++count;
		}
		count=1;
		while(x+count<n&&y-count>=0) {
			if(board[x+count][y-count])
				return false;
			++count;
		}
		count=1;
		while(y+count<n&&x-count>=0) {
			if(board[x-count][y+count])
				return false;
			++count;
		}
		return true;
		
	}

}
